package com.formula.datastructure.exercise.graph.undirect.sp;

import com.formula.datastructure.exercise.graph.undirect.ListEdge;
import com.formula.datastructure.exercise.graph.undirect.ListGraph;
import com.formula.datastructure.exercise.graph.undirect.MatrixGraph;
import com.formula.datastructure.util.DataUtil;

// 这个是计算所有顶点的距离
public class Floyd {

    // 不要用Max, 容易溢出成为负值
    private static final int INF = 99999;

    // 距离
    public int[][] distance;
    // 前驱表, 每一行就是表示这一行到其他点是通过哪一个中间节点到的
    public int[][] prev;

    /**
     * 三层for循环
     * <p>
     * 2张二维表, 距离表和前驱表
     */
    public void shortestPath(MatrixGraph graph) {
        int N = graph.size;

        // 初始化, 从代码角度来说, 必须深度复制
        distance = new int[N][N];

        // 刚开始所有的顶点都是通过自己到达的
        prev = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                prev[i][j] = i;
                // 必须深度复制
                distance[i][j] = graph.edges[i][j];
            }
        }

        /**
         * 先把最核心思想捋一遍
         * min(dis(i,j), dis(i,k) + dis(j,k))
         *
         * 记得先写中间节点k, 再写起点, 最后写终点
         */

        //三个for框架先搭起来
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        prev[i][j] = k;
                    }
                }
            }
        }
    }

    // 其实如果是邻接链表, 就需要把它转换为邻接矩阵
    public void shortestPath(ListGraph graph) {
        int N = graph.vertexSize();
        distance = new int[N][N];
        prev = new int[N][N];

        // 初始化
        for (int i = 0; i < N; i++) {
            // 第i个顶点的第一条边
            ListEdge tempEdge = graph.vertexList[i].firstEdge;
            while (tempEdge != null) {
                distance[i][tempEdge.toIdx] = tempEdge.weight;
                distance[tempEdge.toIdx][i] = tempEdge.weight;
                tempEdge = tempEdge.nextEdge;
            }
        }

        // 3个for
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        prev[i][j] = k;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        MatrixGraph graph = new MatrixGraph();
        graph.insertVex("A");
        graph.insertVex("B");
        graph.insertVex("C");
        graph.insertVex("D");
        graph.insertVex("E");
        graph.insertVex("F");
        graph.insertVex("G");
        for (int i = 0; i < graph.size; i++) {
            //Arrays.fill(graph.edges[i], INF);
            graph.insertEdge(i, i, 0);
        }

        graph.insertEdge(0, 1, 5);
        graph.insertEdge(0, 2, 7);

        graph.insertEdge(1, 4, 4);
        graph.insertEdge(1, 5, 3);

        graph.insertEdge(2, 3, 6);
        graph.insertEdge(2, 6, 4);

        graph.insertEdge(3, 4, 4);
        graph.insertEdge(3, 5, 2);

        graph.insertEdge(4, 2, 8);
        graph.insertEdge(4, 6, 3);

        Floyd sp = new Floyd();
        sp.shortestPath(graph);
        DataUtil.print2Array(graph.edges, graph.size);
        System.out.println();
        DataUtil.print2Array(sp.distance, graph.size);
        System.out.println();
        DataUtil.print2Array(sp.prev, graph.size);
    }
}
